#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include"dlist.h"


//不改变结构就是定义成头节点的后继节点
//改变结构的就是定义成头节点

//双向链表需要注意多级指针

//初始化
void InitList(DList plist)
{
	assert(plist != NULL);
	if (plist == NULL)
		return;

	plist->next = NULL;
	plist->prio = NULL;
}

/*在双向链表的头部插入节点时，需要进行参数判断新节点的后继指针是否为空的原因有几个：

1. 确保链表的完整性：在插入节点时，需要确保链表的结构保持完整性。如果新节点的后继指针不为空，
说明原链表中存在节点，那么需要修改原链表中第一个节点的前驱指针指向新节点，
同时修改新节点的后继指针指向原来的第一个节点，从而建立正确的连接关系。

2. 避免空指针错误：在程序设计中，空指针错误是常见的 bug 之一。通过判断新节点的后继指针是否为空，
可以避免在操作链表时出现空指针错误，提高代码的健壮性和可靠性。

3. 处理特殊情况：在某些情况下，可能需要特殊处理链表的头部插入操作。
例如，如果链表为空，那么新节点就成为链表的唯一节点，此时新节点的后继指针应该为空。通过参数判断
新节点的后继指针是否为空，可以方便地处理这种特殊情况。

因此，通过参数判断新节点的后继指针是否为空，可以确保在双向链表的头部插入操作中正确处理各种情况，
保证链表结构的正确性和代码的稳定性。
*/

//头插（★★★）
bool Insert_head(DList plist, int val)
{
	assert(plist != NULL);
	if (plist == NULL)
		return false;

	//定义一个节点，并赋值
	DNode* p = (DNode*)malloc(sizeof(DNode));
	assert(p != NULL);
	p->data = val;

	//插入新的节点：
	//注意：4句话，顺序要注意，参数判断也很重要
	// 1.把plist的后继指针赋值给p的后继指针
	// 2.把plist的地址赋值给p的前驱指针
	// 3.把p的地址赋值给plist的后继指针
	// 4.把p的地址赋值给p的后继节点的前驱指针
	p->next = plist->next;//先绑后面的，保证数据是存在的
	plist->next = p;
	p->prio = plist;

	if(p->next!=NULL)//很重要  如果是空表就会崩溃
		p->next->prio = p;//多级指针（多想一下）如果为空，会奔溃
	return true;
}

//尾插（★★★）
bool Insert_tail(DList plist, int val)
{
	//参数判断
	assert(plist != NULL);
	if (plist == NULL)
		return false;
	//定义新的节点
	DNode* p = (DNode*)malloc(sizeof(DNode));
	assert(p != NULL);
	p->data = val;

	//找尾巴
	DNode* q = plist;
	while (q->next != NULL)
	{
		q = q->next;
	}

	//插入
	p->next = q->next;
	p->prio = q;
	q->next = p;
	return true;
}
//在plist中查找第一个key值，找到返回节点地址，没有找到返回NULL；
DNode* Search(DList plist, int key)
{
	//不修改结构，定义成头节点的后继节点
	for (DNode* p = plist->next; p != NULL; p = p->next)
	{
		if (p->data == key)
		{
			return p;
		}
	}
	return NULL;
}



//删除第一个val的值（★★★）
bool DelVal(DList plist, int val)
{
	assert(plist != NULL);
	if (plist == NULL)
		return false;


	//找到val值所在的位置在哪里
	DNode* p = Search(plist, val);
	if (p == NULL)
		return false;
	//这里的p->prio不会为空
	p->prio->next = p->next;
	if(p->next!=NULL)//参数判断很重要（★★★）
		p->next->prio = p->prio;
	free(p);

	return true;

}

//插入数据，在plist链表的pos位置插入val;
//注意：1.题目不说，插入的位置就是从0开始
//		2.插入位置，插入在2号位置的前面，取代掉2号位置的数据
//比如在2号位置，插入10，新的数据10会重新取代2号位置的数据
//0 1 2 3 4 5 6 7 8 9
//0 1 10 2 3 4 5 6 7 8 9
bool Insert(DList plist, int pos, int val)
{
	//判空
	assert(plist != NULL);
	if (plist == NULL)
		return false;
	//申请节点p
	DNode* p = (DNode*)malloc(sizeof(DNode));
	assert(p != NULL);
	p->data = val;

	//找位置q
	DNode* q = plist;
	int i = 0;
	while (i < pos)
	{
		i++;
		q = q->next;
	}

	//插入数据
	//将p插入到q的后面
	p->next = q->next;
	q->next = p;
	p->prio = q;
	if (p->next != NULL)
		p->next->prio = p;

	return true;
}

//判空
bool IsEmpty(DList plist)
{
	return plist->next == NULL;
}

//获取数据节点的个数
int GetLength(DList plist)
{
	assert(plist != NULL);
	if (plist == NULL)
		return false;

	int count = 0;
	DNode* p = plist->next;
	while (p!=NULL)
	{
		p = p->next;
		count++;
	}

	return count;
}


//删除pos位置的值
bool DelPos(DList plist, int pos)
{
	assert(plist != NULL);
	if (plist == NULL)
		return false;

	if (pos < 0 || pos >= GetLength(plist))
		return false;

	//找位置p
	DNode* p = plist;
	int i = 0;
	while (i < pos)
	{
		i++;
		p = p->next;
	}
	DNode* q = p->next;//q是要删除的节点，注意q可能是最后一个点

	//删除
	p->next = q->next;
	if (q->next != NULL)
		q->next->prio = q->prio;

	//释放
	free(q);

	return true;
}



//返回key的前驱地址，如果不存在返回NULL；
DNode* GetPrio(DList plist, int key)
{
	DNode* p = Search(plist, key);

	return p == NULL ? NULL : p->prio;
}
//返回key的后继地址，如果不存在返回NULL；
DNode* GetNext(DList plist, int key)
{
	DNode* p = Search(plist, key);

	return p == NULL ? NULL : p->prio;
}

//输出
void Show(DList plist)
{
	//注意，头节点不能访问data
	for (DNode* p = plist->next; p != NULL; p = p->next)
	{
		printf("%d ", p->data);
	}
	printf("\n");
}

//清空数据
void Clear(DList plist)
{
	Destroy(plist);
}

//销毁整个内存
void Destroy(DList plist)
{
	assert(plist != NULL);
	if (plist == NULL)
		return;
	assert(plist != NULL);
	if (plist == NULL)
		return;
	//总是删除第一个节点
	DNode* p=NULL;
	while (plist->next != NULL)
	{
		p = plist->next;
		plist->next = p->next;
	}
	free(p);
}


//测试的时候，一定要有初始化和销毁函数，初始化是为了避免野指针
//测试双向链表
//在测试的时候，要互补影响，一个一个地测试
//int main()
//{
//	DNode d;//注意：d的内存不是malloc来的，不可以动态释放
//	//初始化
//	InitList(&d);
//
//	//头插
//	for (int i = 0;i < 10;i++)
//	{
//		//Insert_head(&d, i);
//		Insert_tail(&d, i);
//	}
//	Show(&d);
//
//	//普通插入
//	Insert(&d, 2, 10);
//	Show(&d);
//}